/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.Iterator;
import java.util.Stack;
import java.util.EmptyStackException;
import java.util.NoSuchElementException;

import mosdi.util.TreeNode;

public class PostOrderIterator<T extends TreeNode> implements Iterator<T> {
	private Stack<Iterator<? extends TreeNode>> iteratorHistory;
	private Stack<T> nodeHistory;
	private T nextNode;
	private int minDepth;
	private int maxDepth;
	private int nextDepth;
	private int lastDepth;
	
	public PostOrderIterator(T node) {
		minDepth=-1;
		maxDepth=-1;
		nextDepth=0;
		lastDepth=-1;
		setUp(node);
	}

	/** Construct a constrained iterator which only returnes nodes
	 *  whose depth lies in [minDepth..maxDepth]. If either parameter
	 *  is -1, respective constraint is turned of. */
	public PostOrderIterator(T node, int minDepth, int maxDepth) {
		this.minDepth=minDepth;
		this.maxDepth=maxDepth;
		setUp(node);
	}
	
	public boolean hasNext() {
		return nextNode!=null;
	}

	private void setUp(T root) {
		iteratorHistory = new Stack<Iterator<? extends TreeNode>>();
		nodeHistory = new Stack<T>();
		T node = root;
		nextDepth=0;
		while (node.hasChild()) {
			if (nextDepth==maxDepth) break;
			nodeHistory.push(node);
			Iterator<? extends TreeNode> iter = node.children();
			iteratorHistory.push(iter);
			node=(T)iter.next();
			++nextDepth;
		}
		nextNode=node;
	}
	
	private void step() {
		while (nextNode!=null) {
			try {
				Iterator<? extends TreeNode> iter = iteratorHistory.peek();
				if (iter.hasNext()) {
					T node = (T)iter.next();
					nextDepth=iteratorHistory.size();
					while (node.hasChild()) {
						if (nextDepth==maxDepth) break;
						nodeHistory.push(node);
						iter=node.children();
						iteratorHistory.push(iter);
						node=(T)iter.next();
						++nextDepth;
					}
					nextNode=node;
				} else {
					nextNode=nodeHistory.pop();
					iteratorHistory.pop();
					nextDepth=iteratorHistory.size();
				}
			} catch (EmptyStackException e) {
				nextNode=null;
			}
			if ((minDepth>=0) && (nextDepth<minDepth)) continue;
			if ((maxDepth>=0) && (nextDepth>maxDepth)) continue;
			return;
		}
	}
	
	public T next() {
		if (nextNode!=null) {
			lastDepth = nextDepth;
			T result = nextNode;
			step();
			return result;
		}
		else throw new NoSuchElementException();
	}

	/** Returns the depth of node last returned by next(). */
	public int getDepth() {
		return lastDepth;
	}
	
	public void remove() { throw new UnsupportedOperationException(); }
}
